package leetcode;

/**
 * Created by Ghost on 2014/10/7.
 */
public class Insertion_Sort_List {
    public static ListNode insertionSortList(ListNode head) {
        if(head==null)
            return null;
        ListNode newHead = new ListNode(head.val);

        ListNode current = head.next;

        ListNode newPre = null;

        while(current!=null){
            ListNode tmp = newHead;
            while(tmp!=null && tmp.val<=current.val){
                newPre = tmp;
                tmp = tmp.next;
            }
            if(tmp==null){
                newPre.next = new ListNode(current.val);
            }
            else {
                if(tmp != newHead){
                    ListNode t = new ListNode(current.val);
                    t.next = tmp;
                    newPre.next = t;
                }
                else{
                    ListNode t = new ListNode(current.val);
                    t.next = newHead;
                    newHead = t;
                }

            }
            current = current.next;
        }
        return newHead;
    }
    public static void main(String[] args){
//        ListNode head = new ListNode(1);
//        head.next = new ListNode(3);
//        head.next.next = new ListNode(2);
//        head.next.next.next = new ListNode(0);

        ListNode tmp = insertionSortList(null);
        while(tmp!=null){
            System.out.println(tmp.val);
            tmp = tmp.next;
        }
    }
}
